package com.algorithm.ch1.cjm.linkedlist;

import com.algorithm.ch1.cjm.linkedlist.model.ListNode;

/**
 * 删除链表的倒数第N个节点
 * <p>
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 * <p>
 * 示例：
 * <p>
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 * <p>
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 */
public class RemoveNthFromEnd {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        removeNthFromEnd1(node1, 1);


//        ListNode nodeA = new ListNode(1);
//        ListNode nodeB = new ListNode(2);

//        nodeA.next = nodeB;

//        removeNthFromEnd1(nodeA, 1);
    }

    /**
     * 1.求链表长度
     * 2.删除链表
     * T(n) = n + n
     * f(n) = n
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {

        //求数组长度
        int length = 0;
        ListNode node = head;
        while (node != null){

            node = node.next;
            length ++;
        }

        //节点索引
        int index = length - n;
        int i = 0;

        ListNode preNodeA = null;
        ListNode nodeA = head;

        while (i < index){

            preNodeA = nodeA;
            nodeA =  nodeA.next;
            i ++;
        }

        if(preNodeA == null){

            if(nodeA.next != null){
                nodeA.val = nodeA.next.val;
                nodeA.next = nodeA.next.next;
            }else {
                head = null;
            }

        }else {

            if(nodeA != null){
                preNodeA.next = nodeA.next;
            }
        }

        ListNode.print(head);
        return head;
    }

    /**
     * 第二版
     * T(n) = n;
     * f(n) = n;
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd1(ListNode head, int n){

        if(n == 0){
            return head;
        }

        //构造一个假的链表头
        if (n == 0) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy, cur = dummy;
        while( n >= 0 && cur != null) {
            cur = cur.next;
            n --;
        }
        while (cur != null) {
            pre = pre.next;
            cur = cur.next;
        }

        pre.next = pre.next.next;

        return dummy.next;
    }

}

